package binary_tree.leetcode;

import java.util.Scanner;

/**
 * 根据前序遍历结果构建二叉树
 * @Author Stark
 * @Date 2022/3/2 16:49
 */
public class NowCoder_BuildTreeByPrevOrder {
    //定义一个索引用来取出字符串中的字符
    private static int index = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()){
            String str = scanner.nextLine();
            inOrder(biuldTree(str));
            index = 0;
        }
    }

    private static void inOrder(TreeNode root) {
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    private static TreeNode biuldTree(String str) {
        if(str.charAt(index) == '#'){
            index++;
            return null;
        }
        //根据前序遍历的结果构建二叉树
        TreeNode node = new TreeNode(str.charAt(index++));
        node.left = biuldTree(str);
        node.right = biuldTree(str);
        return node;
    }
}
